/* 
 * File:   seq_gen.h
 * Author: TuanND
 *
 * Created on September 6, 2013, 3:25 PM
 * 
 * ABSTRACT
 * This is simply a Hamming Sequence Generator Library. What's Hamming Sequence? Please searching
 * on online resources and book. Here's an example (http://en.wikipedia.org/wiki/Regular_number).
 * Hereby I just will describe key points in my program (implementation).
 * 
 * DATA STRUCTURE
 * First, I defined two types: hNum (Hamming Number) and hList (Hamming List). 
 * struct hNum
 * {
 *   int num;
 *   struct hNum* next;
 * };
 * struct hList
 * {
 *   struct hNum* start;//point to the first element
 *   struct hNum* end;//point to the last element
 * };
 * Each hNum instance will have a number and a pointer to the next hNum in a list. 
 * A hList instance will have a pointer to the start of list and another pointer to the end of list.
 * 
 * LIST OPERATIONS
 * Second, we also defined some needed functions (basic list operations) to manipulate 
 * the list such as create (initialize) the list, add a new number to list or print the list...
 * struct hList* list_new(void);
 * struct hList* list_add(struct hList*, const int);
 * void list_print(const struct hList*);
 * struct hList* list_scale(struct hList *pList, const int scale);
 * struct hList* list_sub(struct hList* pList, int length);
 * 
 * ALGORITHM FUNCTIONS
 * The heart of my program is algorithm function named sequence_generator. This function
 * takes the input N as the length of Hamming sequence required by users
 * and return exactly a sequence with length N. This sequence_generator calls to merge_list
 * and check_list to merge 2 separate sorted list into one list and check the safe length can be extract.
 * For example: struct hList* pHS = sequence_generator(5) will return {2,3,4,5,6}.
 * 
 * FOR DETAIL IMPLEMENTATION DESCRIPTION, PLEASE LOOK AT FILE seq_gen.c
 * 
 */

#ifndef SEQ_GEN_H
#define	SEQ_GEN_H

#ifdef	__cplusplus
extern "C" {
#endif

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#ifdef	__cplusplus
}
#endif

#endif	/* SEQ_GEN_H */

/******************************************************************************
 * DATA STRUCTURE
 ******************************************************************************/
/*
 * Hamming Number structure, each contains a number and point to next number
 */
struct hNum
{
    long num;
    struct hNum* next;
};

/*
 * List Type, a common type for all five list used in algorithm
 * We want a FIFO list, so we need 2 pointers (start, end) for each list
 */
struct hList
{
    struct hNum* start;//point to the first element
    struct hNum* end;//point to the last element
};

/******************************************************************************
 * LIST OPERATIONS (AS A LIB)
 ******************************************************************************/

/**
 * Initialize a list, just like a new operation in OOP. You need to call this
 * before doing anything with the list.
 * E.g : struct hList* newlist = list_new();
 * @return a initialized list
 */
struct hList* list_new(void);

/**
 * Add a new element to existing list. The new element will be appended to the end
 * of list. Return value may be not necessary in most of case except in the case you
 * want to duplicate the list
 * E.g : list_add(existing_list, 10);
 * @param in/out hList* the existing list and the list after appended
 * @param int the new element to append
 * @return the list after appended
 */
struct hList* list_add(struct hList*, const long);

/**
 * Print a linked list on screen.
 * @param hList* input list to print
 */
void list_print(const struct hList*);

/**
 * Extract a sub-list from a longer list. The sub-list is just a prefix of the original
 * list.
 * @param pList: a longer list
 * @param length: length of prefix
 * @return : a prefix list length
 */
struct hList* list_sub(struct hList* pList, int length);

/**
 * Time a list with a scale factor.
 * @param pList: list to scale
 * @param scale: scale factor
 * @return a new list after scaled input list
 */
struct hList* list_scale(struct hList *pList, const int scale);

/*******************************************************************************
 * ALGORITHM FUNCTIONS
 ******************************************************************************/

/**
 * Generate a Hamming sequence given length N
 * For example: struct hList* pH =  sequence_generator(4); will return a list which
 * includes {2, 3, 4, 5}.
 * @param N: number of Hamming numbers
 * @return : a list of N Hamming numbers
 */
struct hList* sequence_generator(int N);

/**
 * Merge 2 sorted lists into a sorted list. With A, B is two sorted list, this
 * function will return a list C which includes all elements from both A, B
 * @param pListA
 * @param pListB
 * @return : combined list
 */
struct hList* merge_list(struct hList *pListA, struct hList *pListB);
/**
 * Given a Final List at step K, this function will return the number of first elements
 * in list is continuous Hamming number.
 * For example: given final list {2, 3, 4, 5, 6, 9, 10, 15, 25}. This function will return 
 * 5, which is the maximum continuous Hamming number {2,3,4,5,6}.
 * @param pList
 * @param step
 * @param hCount
 * @return 
 */
struct hNum* check_list(struct hList *pList, int step, int* hCount);